Discrete Mathematics: The Anatomy of a Mathematical System

Imagine building a skyscraper. You cannot start with the penthouse; you need a foundation so deep it rests on the earth's mantle. In mathematics, this foundation is the Mathematical System. It is a formal linguistic structure designed to determine truth without falling into the trap of circular reasoning. It is the "Logic Pyramid" where every stone is supported by the one beneath it.

The Hierarchy of Mathematical Truth

A mathematical system consists of four primary vertical layers, each serving a distinct structural purpose:

1. The Foundation: Undefined Terms & Axioms

To avoid an infinite regress (defining a word with a word, which needs another definition), we accept certain Undefined Terms as primitive concepts (e.g., "point" or "set"). We also accept Axioms: statements assumed true without proof.

Example: In Euclidean Geometry, we accept the axiom that a straight line segment can be drawn joining any two points.

2. The Framework: Definitions

Definitions are agreed-upon descriptions of new concepts using axioms and undefined terms. A mathematical system is explicitly "A collection of axioms, definitions, and undefined terms.".

3. The Bridge: Proofs

A Proof is the formal argument that chains axioms and definitions together to validate a theorem. It is the logical mechanism that transforms a conjecture into an established fact.

4. The Crown: Theorems, Lemmas, & Corollaries

Theorem: A significant proposition that has been proved true (e.g., "If two sides of a triangle are equal, then the angles opposite them are equal.").
Lemma: A tactical "stepping stone"—a theorem not interesting on its own but vital for proving a larger result.
Corollary: "Low-hanging fruit"—a theorem that follows easily and immediately from another theorem.

Example: The Isosceles Architecture

In the system of Euclidean Geometry:

Theorem: If two sides of a triangle are equal, then the angles opposite them are equal.
Corollary: If a triangle is equilateral, then it is equiangular. (This follows with almost no additional effort from the theorem above).
Advanced Application: In quadrilateral systems, we might prove: "If the diagonals of a quadrilateral bisect each other, then the quadrilateral is a parallelogram."

🎯 Core Principle

Mathematical systems are designed to eliminate ambiguity. By establishing a rigid hierarchy from Undefined Terms up to Corollaries, we ensure that every "truth" can be traced back to its immutable foundation without circularity.

QUESTION 1

Which component of a mathematical system is assumed to be true without any proof?

Theorem

Lemma

Axiom

Corollary

QUESTION 2

What is the primary distinction between a Lemma and a Corollary?

Lemmas are assumed true, Corollaries are proved.

Lemmas are 'stepping stones' for larger proofs; Corollaries follow easily from a proven theorem.

Corollaries are harder to prove than Lemmas.

A Lemma is a type of axiom.

QUESTION 3

Why does a mathematical system require 'Undefined Terms'?

To allow for multiple interpretations of the system.

To avoid an infinite regress of definitions.

Because math is inherently imprecise.

To simplify the complexity of theorems.

QUESTION 4

How do you disprove a universally quantified statement like 'For all x, P(x)'?

By proving it for at least ten cases.

By showing it is true for most values.

By providing a single counterexample.

By proving the negation is an axiom.

QUESTION 5

Based on Euclidean Geometry, which of these is an Axiom?

An equilateral triangle is equiangular.

A straight line segment can be drawn joining any two points.

The sum of angles in a triangle is 180 degrees.

Vertical angles are equal.

Challenge: Operating the System

From Foundations to Computation

Understanding the "Anatomy" is the prerequisite for the "Operation" of proofs. Apply the logic of mathematical systems to solve these diverse proof and algorithmic challenges.

[Computational Logic] Write a program to determine whether $X \subseteq Y$, given arrays representing $X$ and $Y$. (Required Output: ~150 words)

Reference Solution:
To determine if $X$ is a subset of $Y$ ($X \subseteq Y$), we follow the formal definition: $\forall x \in X, x \in Y$. The algorithm iterates through every element in array $X$. For each element, it performs a search (linear or binary, depending on sorting) in array $Y$. If any element of $X$ is not found in $Y$, the program immediately returns false, as the universal condition is violated. If the loop completes for all elements of $X$ without such a failure, the program returns true.

In terms of efficiency, a naive nested loop results in $O(n \cdot m)$ complexity. For large sets, sorting both arrays first or using a Hash Set for $Y$ allows for $O(n + m)$ average time complexity. This algorithmic check is the computational equivalent of a direct proof for set inclusion.

[Proof by Cases] Use proof by cases to prove that $|xy| = |x||y|$ for all real numbers $x$ and $y$.

Model Solution:
We divide the real number line into exhaustive scenarios based on the sign of $x$ and $y$:

Case 1 ($x \ge 0, y \ge 0$): $|x|=x, |y|=y, xy \ge 0$, so $|xy|=xy$. Matches $|x||y|$.
Case 2 ($x < 0, y < 0$): $|x|=-x, |y|=-y, xy > 0$, so $|xy|=xy$. Since $(-x)(-y)=xy$, it matches $|x||y|$.
Case 3 ($x \ge 0, y < 0$): $|x|=x, |y|=-y, xy \le 0$, so $|xy|=-(xy)$. Since $x(-y)=-xy$, it matches $|x||y|$.
Case 4 ($x < 0, y \ge 0$): Symmetric to Case 3. $|xy|=-(xy) = (-x)y = |x||y|$.

Conclusion: In all exhaustive cases, the equality holds.

[Induction] Prove that $H_1 + H_2 + \dots + H_n = (n + 1)H_n - n$ for all $n \ge 1$, where $H_n$ is the $n$-th harmonic number.

Grading Rubric / Reference Answer:
1. Basis Step ($n=1$): $H_1 = 1$. Right side: $(1+1)H_1 - 1 = 2(1) - 1 = 1$. Matches.
2. Inductive Hypothesis: Assume $\sum_{i=1}^k H_i = (k+1)H_k - k$ is true for some $k \ge 1$.
3. Inductive Step: Show $\sum_{i=1}^{k+1} H_i = (k+2)H_{k+1} - (k+1)$.
- $\sum_{i=1}^{k+1} H_i = [\sum_{i=1}^k H_i] + H_{k+1} = (k+1)H_k - k + H_{k+1}$.
- Note $H_{k+1} = H_k + \frac{1}{k+1}$, so $H_k = H_{k+1} - \frac{1}{k+1}$.
- Substitute: $(k+1)(H_{k+1} - \frac{1}{k+1}) - k + H_{k+1} = (k+1)H_{k+1} - 1 - k + H_{k+1}$.
- Group terms: $(k+1+1)H_{k+1} - (k+1) = (k+2)H_{k+1} - (k+1)$. $\square$